#include <cstdio>

int max( int a, int b ) { return ( a < b )?b :a; }
int min( int a, int b ) { return ( a < b )?a :b; }

struct Node
{
    int v, w;
    Node( ) { }
    Node( int _v, int _w )
        : v( _v ), w( _w ) { }
};

int T, MaxP, W, AP[ 2001 ], BP[ 2001 ], AS[ 2001 ], BS[ 2001 ], f[ 2001 ][ 2001 ];
Node q[ 2001 ];

void init( )
{
    int i, j;
    scanf("%d%d%d", &T, &MaxP, &W);
    for ( i = 1; i <= T; i++ )
        scanf("%d%d%d%d", &AP[ i ], &BP[ i ], &AS[ i ], &BS[ i ]);
    for ( i = 0; i <= T; i++ )
        for ( j = 0; j <= MaxP; j++ )
            f[ i ][ j ] = -0x7fffffff;
    for ( i = 1; i <= T; i++ )
        for ( j = 0; j <= min( MaxP, AS[ i ] ); j++ )
            f[ i ][ j ] = -j * AP[ i ];
    for ( i = 1; i <= T; i++ )
        for ( j = 0; j <= MaxP; j++ )
            f[ i ][ j ] = max( f[ i ][ j ], f[ i - 1 ][ j ] );
}

void work( )
{
    int head, tail, i, j;
    for ( i = W + 2; i <= T; i++ )
    {
        head = 0;
        tail = -1;
        for ( j = 0; j <= MaxP; j++ )
        {
            f[ i ][ j ] = max( f[ i ][ j ], f[ i - 1 ][ j ] );
            while ( head <= tail && f[ i - W - 1 ][ j ] + j * AP[ i ] > q[ tail ].v )
                tail--;
            q[ ++tail ] = Node( f[ i - W - 1 ][ j ] + j * AP[ i ], j );
            while ( head <= tail && j - q[ head ].w > AS[ i ] )
                head++;
            if ( head <= tail )
                f[ i ][ j ] = max( f[ i ][ j ], q[ head ].v - j * AP[ i ] );
        }
        head = 0;
        tail = -1;
        for ( j = MaxP; j >= 0; j-- )
        {
            f[ i ][ j ] = max( f[ i ][ j ], f[ i - 1 ][ j ] );
            while ( head <= tail && f[ i - W - 1 ][ j ] + j * BP[ i ] > q[ tail ].v )
                tail--;
            q[ ++tail ] = Node( f[ i - W - 1 ][ j ] + j * BP[ i ], j );
            while ( head <= tail && q[ head ].w - j > BS[ i ] )
                head++;
            if ( head <= tail )
                f[ i ][ j ] = max( f[ i ][ j ], q[ head ].v - j * BP[ i ] );
        }
    }
}

void print( )
{
    int i, ret = 0;
    for ( i = 0; i <= MaxP; i++ )
        ret = max( ret, f[ T ][ i ] );
    printf("%d\n", ret);
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
        print( );
    }
    return 0;
}
